Cryptographic algorithms are widely used for encryption of messages, authentication, encryption signatures and identification. The well-known DES (Data Encryption Standard) has been in use for a long time, and was updated by Triple-DES, which has been replaced in many applications by the AES (Advanced Encryption Standard).
DES, Triple-DES and AES are exemplary symmetric block ciphers. Block ciphers operate on blocks of plaintext and ciphertext, usually of 64 or 128 bits but sometimes longer. Stream ciphers are the other main type of cipher and operate on streams of plain text and cipher text 1 bit or byte (sometimes one word) at a time. With a block cipher, a particular plain text block will always be encrypted to the same cipher text block using the same key. However; to the contrary with a stream cipher, the same plain text bit or byte will be encrypted to a different bit or byte each time it is encrypted. Hence in the ECB (electronic code book) mode for block ciphers, each plain text block is encrypted independently.
AES is approved as an encryption standard by the U.S. Government. Unlike DES, it is a substitution permutation network. AES is fast to execute in both computer software and hardware implementation, relatively easy to implement, and requires little memory. AES has a fixed block size of 128 bits and a key size of 128, 192 or 256 bits. Due to the fixed block size of 128 bits, AES operates on a 4×4 array of bytes. It uses key expansion and like most block ciphers a set of encryption and decryption rounds (iterations). Each round involves the same processes. Use of multiple rounds enhances security. Block ciphers of this type use in each round a substitution box or s-box. This operation provides non-linearity in the cipher and significantly enhances security.
Note that these block ciphers are symmetric ciphers, meaning the same algorithm and key are used for encryption and decryption, except usually for minor differences in the key schedule. As is typical in most modern ciphers, security rests with the (secret) key rather than the algorithm. The s-boxes or substitution boxes were introduced in DES and accept an n bit input and provide an m bit output. The values of m and n vary with the cipher. The input bits specify an entry in the s-box in a particular manner well known in the field.
To implement AES (having 128 bit blocks, and 10 rounds) arithmetically involves the following operations: (1) 11 AddRoundKey operations (1 prior to 10 rounds); (2) 10 Sub-Byte operations, (3) 10 ShiftRow Operations, and (4) 9 Mix-Column Operations. Each round of rounds 1 to 9 consists of operations (1) to (4), where output from one operation is input to the next operation, and output from operation (4) is input to operation (1). Round 10 consists of operations (1) to (3), where output from operation (3) is the output used. Arithmetic implementations of AES do not provide much security against an attacker recovering a secret key, if the attacker has privileged access to the system implementing the cipher.
Many encryption algorithms are primarily concerned with producing encrypted data that is resistant to decoding by an attacker who can interact with the encryption algorithm only as a “black box” (input-output) model, and cannot observe internal workings of the algorithm or memory contents, etc due to lack of system access. The black box model is appropriate for applications where trusted parties control the computing systems for both encoding and decoding ciphered materials.
However, many applications of encryption do not allow for the assumption that an attacker cannot access internal workings of the algorithm. For example, encrypted digital media often needs to be decrypted on computing systems that are completely controlled by an adversary (attacker). There are many degrees to which the black box model can be relaxed. An extreme relaxation is called the “white box” model. In a white box model, it is presumed that an attacker has total access to the system performing an encryption, including being able to observe directly a state of memory, program execution, and so on. In such a model, an encryption key can be observed in or extracted from memory, and so ways to conceal operations indicative of a secret key are important.
The publication “White-Box Cryptography in an AES implementation” Lecture Notes in Computer Science Vol. 2595, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography pp. 250-270 (2002) by Chow et al. discloses implementations of AES that obscure the operations performed during AES by using table lookups to obscure the secret key within the lookup tables, and obscure intermediate state information that would otherwise be available in arithmetic implementations of AES.
Chow et al. (for his “white box” implementation where the key is known at the computer code compilation time) uses 160 separate tables to implement the 11 AddRoundKey operations and 10 SubByte Operations (10 rounds, with 16 tables per round, where each table is for 1 byte of the 16 byte long—128 bit—AES block). These 160 tables embed a particular AES key, such that output from lookups involving these tables embeds data that would normally result from the AddRoundKey and SubByte operations of the AES algorithm, except that this data includes input/output permutations that make it more difficult to determine what parts of these tables represent round key information derived from the AES key.
Chow et al. uses 1008 separate tables to implement the nine MixColumn Operations (there is no MixColumn operation in the 10th round of AES). One type of these tables implements a multiplication of one byte with the AES MixColumn polynomial (per the specification), and another type implements the logical XOR (exclusive OR) part of MixColumn. Each table is used once during the nine rounds.
The Chow et al. solution is clever, but several attacks already have been made on it. Chow et al.'s white-box implementation of a given block cipher encryption process decomposes the block cipher (with its key) as a set of table-lookups. The table-lookups are then masked using permutation functions. (A permutation as used here refers to a bijection operation that changes the order of bits in a data byte or word in a predetermined fashion.) This is explained in Chow et al., and this method can be extended to any block cipher.
The most recent and the most powerful such extension was published by Olivier Billet et al. “Cryptanalysis of a White Box AES Implementation” in SAC 2004, LNCS 3357 pp. 227-240, 2005. The details of the processed basic operations are necessary to mount this attack. This means the attacker has to distinguish the set of operations to extract the operations per rounds, the MixColumn operation, etc.